package com.tgy.leetcode;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/8/20 9:43 AM
 *
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class _106_从中序与后序遍历序列构造二叉树_stack_02 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (inorder == null || postorder == null || inorder.length != postorder.length ) {

            return null;
        }

        if (inorder.length == 0) {

            return null;
        }


        TreeNode root = new TreeNode(postorder[postorder.length - 1]);

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        int inorderIndex = inorder.length - 1;

        /**
         * 从 postorder.length - 2 开始是因为 postorder.length - 1 已经在栈中，
         * 本次比较获取栈中元素与inoder[inorderIndex]对比
         */
        for (int i = postorder.length - 2; i >= 0 ; i--) {

            int preVal = postorder[i];

            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {

                node.right = new TreeNode(preVal);
                stack.push(node.right);
            }else {

                while (!stack.isEmpty() && (stack.peek().val == inorder[inorderIndex])) {

                    node = stack.pop();
                    inorderIndex--;
                }

                node.left = new TreeNode(preVal);
                stack.push(node.left);
            }

        }

        return root;
    }

}
